package com.dmall.graph.bfs.app;

import java.util.LinkedList;
import java.util.Queue;

public class Leetcode1091 {

    private int N;
    private int[][] dirs = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

    public int shortestPathBinaryMatrix(int[][] grid) {
        N = grid.length;
        boolean[][] visited = new boolean[N][N];
        int[][] dis = new int[N][N];

        if (grid[0][0] == 1) {
            return -1;
        }

        if (N == 1) {
            return 1;
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        dis[0][0] = 1;
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            Integer cur = queue.remove();
            int x = cur / N;
            int y = cur % N;
            for (int i = 0; i < dirs.length; i++) {
                int nextx = x + dirs[i][0];
                int nexty = y + dirs[i][1];
                if (inArea(nextx, nexty) && !visited[nextx][nexty] && grid[nextx][nexty] == 0) {
                    int next = nextx * N + nexty;
                    queue.add(next);
                    visited[nextx][nexty] = true;
                    dis[nextx][nexty] = dis[x][y] + 1;
                    if (nextx == N - 1 && nexty == N - 1) {
                        return dis[nextx][nexty];
                    }
                }
            }
        }

        return -1;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }

    public static void main(String[] args) {
        int[][] grid = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};
        Leetcode1091 leetcode1091 = new Leetcode1091();
        System.out.println(leetcode1091.shortestPathBinaryMatrix(grid));
    }
}
